P5176 公约数

首先有一个结论：

$gcd(i\cdot j,i\cdot k,j\cdot k)=\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)}$

证明如下：

先将 $i,j,k$ 用唯一分解定理展开的次方分别为 $w_1,w_2,w_3$。

$gcd(i \cdot j,j \cdot k,i \cdot k)=\sum_{i=1}^k {p_i}^{min(w_{1i}+w_{2i},w_{2i}+w_{3i},w_{1i}+w_{3i})}$

$gcd(i,j) \cdot gcd(j,k) \cdot gcd(i,k)=\sum_{i=1}^k {p_i}^{min(w_{1i},w_{2i})+min(w_{2i},w_{3i})+min(w_{1i},w_{3i})}$

$gcd(i,j,k)=\sum_{i=1}^k {p_i}^{min(w_{1i},w_{2i},w_{3i})}$

$gcd(i\cdot j,i\cdot k,j\cdot k)=\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)}$

$\Leftarrow \sum_{i=1}^k {p_i}^{min(w_{1i}+w_{2i},w_{2i}+w_{3i},w_{1i}+w_{3i})}=\frac{\sum_{i=1}^k {p_i}^{min(w_{1i},w_{2i})+min(w_{2i},w_{3i})+min(w_{1i},w_{3i})}}{\sum_{i=1}^k {p_i}^{min(w_{1i},w_{2i},w_{3i})}}$

$\Leftarrow \sum_{i=1}^k {min(w_{1i}+w_{2i},w_{2i}+w_{3i},w_{1i}+w_{3i})}=\sum_{i=1}^k {min(w_{1i},w_{2i})+min(w_{2i},w_{3i})+min(w_{1i},w_{3i})-min(w_{1i},w_{2i},w_{3i})}$

这是一个轮换式 ， 不妨令 $w_{1i} \le w_{2i} \le w_{3i}$ , 则有

$\Leftarrow \sum_{i=1}^k {w_{1i}+w_{2i}}=\sum_{i=1}^k {w_{1i}+w_{2i}+w_{1i}-w_{1i}}$

$\Leftarrow \sum_{i=1}^k {w_{1i}+w_{2i}}=\sum_{i=1}^k {w_{1i}+w_{2i}}$

所以原结论成立。

$\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p\gcd(i\cdot j,i\cdot k,j\cdot k)\times \gcd(i,j,k)\times \left(\frac{\gcd(i,j)}{\gcd(i,k)\times \gcd(j,k)}+\frac{\gcd(i,k)}{\gcd(i,j)\times \gcd(j,k)}+\frac{\gcd(j,k)}{\gcd(i,j)\times \gcd(i,k)}\right)$

$\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p\frac{gcd(i , j )\cdot gcd(j , k) \cdot gcd(i,k)}{gcd(i,j,k)}\times \gcd(i,j,k)\times \left(\frac{\gcd(i,j)}{\gcd(i,k)\times \gcd(j,k)}+\frac{\gcd(i,k)}{\gcd(i,j)\times \gcd(j,k)}+\frac{\gcd(j,k)}{\gcd(i,j)\times \gcd(i,k)}\right)$

$\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p gcd(i , j)\cdot gcd(j , k) \cdot gcd(i,k)\times \left(\frac{\gcd(i,j)}{\gcd(i,k)\times \gcd(j,k)}+\frac{\gcd(i,k)}{\gcd(i,j)\times \gcd(j,k)}+\frac{\gcd(j,k)}{\gcd(i,j)\times \gcd(i,k)}\right)$

$\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^p gcd(i , j)^2 \cdot gcd(j , k)^2 \cdot gcd(i,k)^2$

$p \times \sum_{i=1}^n\sum_{j=1}^m gcd(i,j)^2+n \times \sum_{i=1}^m\sum_{j=1}^p gcd(i,j)^2+m \times \sum_{i=1}^n\sum_{j=1}^p gcd(i,j)^2$

现在只需要处理出 $\sum_{i=1}^n\sum_{j=1}^m gcd(i,j)^2$ ，就可以用三次反演解决。

令 $s = min(n,m)$，

$\sum_{i=1}^n\sum_{j=1}^m gcd(i,j)^2$

$\sum_{k=1}^{s}k^2\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=k]$

$\sum_{k=1}^{s}k^2\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor} [gcd(i,j)=1]$

$\sum_{k=1}^{s}k^2 \sum_{d=1}^{\lfloor \frac{s}{k} \rfloor } \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor$

$\sum_{k=1}^{s}\sum_{d=1}^{\lfloor \frac{s}{k} \rfloor } k ^2 \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor$

$\sum_{k=1}^{s}\sum_{kd=1}^{s} k ^2 \mu(d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor$

令 $T=kd$ ,

$\sum_{T=1}^{s}\sum_{k|T} k^2 \mu(\frac{T}{k}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$

$\sum_{T=1}^{s}f(T)\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$

其中 $f(n)=\sum_{k|n} k^2 \mu(\frac{n}{k})$ , 由卷积的性质得该函数为积性函数，考虑如何用线性筛求出其前缀和。

如果 $p$ 是一个质数，那么有：

$f(p)=1^2 \times \mu(p)+p^2 \times \mu(1)=p^2-1$

$f(p^k)=\sum_{i=0}^k p^{2i} \times \mu(p^{k-i})$

又因为当 $k-i \ge 2$ 时，$\mu(p^{k-i})=0$，所以所有有贡献的 $i > k - 2$ , 即 $i=k$ 或 $i=k-1$ 。

$f(p^k)=p^{2k}-p^{2(k-1)}=(p^2-1)p^{2(k-1)}=f(p)p^{2(k-1)}$

观察发现括号内 $p$ 减少了 $k-1$ 次方，系数增加 $p^{2(k-1)}$

所以 $f(p^k)=f(p^{k-1}) \times p^2$

整理一下得：

$f(i \times prime[j])=\begin{cases} f(i) \times f(prime[j]) & (i,prime[j])=1 \\\\ f(i) \times prime[j]^2 & (i,prime[j])\not=1 \end{cases}$

复杂度$\Theta(n+t\sqrt n)$

#include <cstdio>
#include <iostream>
using namespace std; 
#define Mod 1000000007

template<typename _T>
void Read( _T &x ) {
	x = 0; int f = 1;
	char s = getchar( );
	for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
	for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
	x *= f;
}
template<typename _T>
void Write( _T x ) {
	if( x < 0 ) putchar('-') , x = -x;
	if( x >= 10 ) Write( x / 10 );
	putchar( x % 10 + '0' );
}

const int MAXN = 20000000;
int t , n , m , p , k , prime[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
    f[ 1 ] = 1;
    for( int i = 2 ; i <= MAXN ; i ++ ) {
        if( !vis[ i ] ) {
            prime[ ++ k ] = i;
            f[ i ] = ( 1ll * i * i - 1 ) % Mod;
        }
        for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
            vis[ i * prime[ j ] ] = 1;
            if( i % prime[ j ] == 0 ) {
                f[ i * prime[ j ] ] = 1ll * f[ i ] * prime[ j ] % Mod * prime[ j ] % Mod;
                break;
            }
            f[ i * prime[ j ] ] = 1ll * f[ i ] * f[ prime[ j ] ] % Mod;
        }
    }
    for( int i = 2 ; i <= MAXN ; i ++ )
        f[ i ] = ( f[ i ] + f[ i - 1 ] ) % Mod;
}

int solve( int n , int m ) {
    int d = min( n , m ) , Ans = 0;
    for( int l = 1 , r ; l <= d ; l = r + 1 ) {
        r = min( n / ( n / l ) , m / ( m / l ) );
        Ans = ( Ans + 1ll * ( f[ r ] - f[ l - 1 ] + Mod ) % Mod * ( n / l ) % Mod * ( m / l ) % Mod ) % Mod;
    }
    return Ans;
}

int main( ) {
    sieve( );
    Read( t );
    while( t -- ) {
        Read( n ) , Read( m ) , Read( p );
        int Ans = ( 1ll * n * solve( m , p ) % Mod + 1ll * m * solve( n , p ) % Mod + 1ll * p * solve( n , m ) % Mod ) % Mod;
        Write( Ans ) , putchar('\n');
    }
    return 0;
}